package PrefixTree;

import java.util.TreeMap;

/**
 * 更具文件路径字符串数组，生成前缀树
 * 然后深度优先遍历打印
 *
 * @author Liaorun
 */
public class GetFolderTree {

    public static void main(String[] args) {
        print(new String[]{"a\\b\\c", "b\\c\\d"});
    }

    public static class Node {

        public String name;
        public TreeMap<String, Node> nextMap;

        public Node(String name) {
            this.name = name;
            nextMap = new TreeMap<>();
        }
    }


    public static void print(String[] folderPaths) {
        if (folderPaths == null || folderPaths.length == 0) {
            return;
        }

        // 根据字符串，把前缀树建立好，头节点为 head
        Node head = generateFolderTree(folderPaths);

        // 打印
        printProcess(head, 0);
    }

    /**
     * 前缀树的深度优先遍历，打印文件路径
     *
     * @param head
     * @param level
     */
    private static void printProcess(Node head, int level) {
        // 经过的节点都打印，处理根节点 level == 0
        if (level != 0) {
            System.out.println(get2nSpace(level) + head.name);
        }

        // 到一个节点后就把下级先走一遍
        for (Node next : head.nextMap.values()) {
            printProcess(next, level + 1);
        }
    }

    private static String get2nSpace(int level) {

        String res = "";
        for (int i = 1; i < level; i++) {
            res += "  ";
        }
        return res;
    }

    /**
     * 更具文件路径字符串数组，生成前缀树
     *
     * @param folderPaths 文件路径字符串数组
     * @return 头节点
     */
    private static Node generateFolderTree(String[] folderPaths) {
        Node head = new Node("");

        for (String folderPath : folderPaths) {
            String[] path = folderPath.split("\\\\");
            Node cur = head;

            for (int i = 0; i < path.length; i++) {
                if (!cur.nextMap.containsKey(path[i])) {
                    // 当前节点没有走向path[i]字符的路，新建一个
                    cur.nextMap.put(path[i], new Node(path[i]));
                }
                // 当前节点有走向path[i]字符的路，直接走到该字符节点去
                cur = cur.nextMap.get(path[i]);
            }
        }
        return head;
    }
}
